package hu;

import java.util.LinkedList;
import java.util.Queue;

public class test{
    public static void main(String[] args) {
        System.out.println(numIslands(new char[][]{{'1','0'},{'1','0'}}));
    }
    public static int numIslands(char[][] grid) {
        /**
        bfs: 使用队列的思想实现，而dfs则是回溯递归
         */
        int sum = 0;
        for (int i = 0; i < grid.length ; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '1'){
                    bfs(grid, i , j);
                    sum++;
                }
            }
        }
        return sum;
    }
    public static void bfs(char[][] grid, int i, int j){
        Queue<int []> queue = new LinkedList<>();
        queue.add(new int []{i,j});
        while(!queue.isEmpty()){
            int[] index = queue.remove();
            if(index[0] >= 0 && index[0] < grid.length && index[1] >= 0
                    && index[1] < grid[0].length && grid[index[0]][index[1]] == '1'){
                grid[index[0]][index[1]] = '0';
                queue.add(new int[] {index[0] + 1, index[1]});
                queue.add(new int[] {index[0] - 1, index[1]});
                queue.add(new int[] {index[0], index[1] + 1});
                queue.add(new int[] {index[0], index[1] - 1});
            }
        }
    }
}
